package com.leetcode.knapsack;

/**
 * 动态规划空间复杂度的极致优化
 * <p>
 * F(i,C)=max(F(i−1,C),v(i)+F(i−1,C−w(i)))
 *
 * https://blog.csdn.net/chanmufeng/article/details/82955730
 */
public class KnapsackV1_2 {

    private int[][] memo;

    public int solveKS(int[] w, int[] v, int C) {
        int size = w.length;
        if (size == 0) {
            return 0;
        }

        int[] dp = new int[C + 1];

        //初始化第一行
        //仅考虑容量为C的背包放第0个物品的情况
        for (int i = 0; i <= C; i++) {
            dp[i] = w[0] <= i ? v[0] : 0;
        }

        for (int i = 1; i < size; i++) {
            for (int j = C; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
            }
        }

        return dp[C];
    }

    public static void main(String[] args) {
        KnapsackV1_2 testKnapsackV1 = new KnapsackV1_2();

        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};

        System.out.println(testKnapsackV1.solveKS(w, v, 5));
    }

}
